package fun.coding.leetcode;

public class LargestRectangleInHistogram {

	public static void main(String[] args) {
		LargestRectangleInHistogram ins = new LargestRectangleInHistogram();
		int[] test1 = {2,1,5,6,2,3};
		System.out.println(ins.largestRectangleArea(test1));
		
	}
	
	public int largestRectangleArea(int[] height) {
		return 0;
	}
	
	// This is an easy O(N^2) algorithm, so no matter what, you have to cut off at one line, 
	// So pick that line, and go left and right, find the max
	public int largestRectangleAreaONSquare(int[] height) {
		if (height == null || height.length == 0) return 0;
		int maxArea = Integer.MIN_VALUE;
		
		for (int i = 0; i < height.length; i++) {
			int l = 1;
			
			// go left
			int j = i - 1;
			while (j >= 0 && height[j] >= height[i]) {
				l++;
				j--;
			}
			
			// go right
			j = i + 1;
			while (j < height.length && height[j] >= height[i]) {
				l++;
				j++;
			}
			
			maxArea = Math.max(l * height[i], maxArea);
		}
		
		return maxArea;
	}

}
